20.3 KB · ⇊ 6 parts · ⤓ Micron 20.3 KB · ⤓ HTML 140.8 KB

top

Die Bellsche Zahl, Bellzahl oder Exponentialzahl B n {\displaystyle B_{n}} ist die Anzahl der Partitionen einer n {\displaystyle n} -elementigen Menge. Benannt ist sie nach dem Mathematiker Eric Temple Bell. Die Folge B 0 , B 1 , B 2 , B 3 , … … {\displaystyle B_{0},B_{1},B_{2},B_{3},\ldots } beginnt mit

1 , 1 , 2 , 5 , 15 , 52 , 203 , 877 , 4140 , 21147 , 115975 , 678570 , … … {\displaystyle 1,1,2,5,15,52,203,877,4140,21147,115975,678570,\ldots } (Folge A000110 in OEIS)

• Bedeutung

• Partitionen

• Multiplikative Partitionen

• Eigenschaften

• Definition

• Erzeugende Funktionen

• Kongruenzsätze

• Asymptotik

• Bellsches Dreieck

• Bellsche Primzahlen

• Einzelnachweise

• Literatur

• Weblinks

→

Hauptartikel

:

Partition (Mengenlehre)

Eine Partition P {\displaystyle P} einer Menge M {\displaystyle M} ist eine Menge nichtleerer, paarweise disjunkter Teilmengen von M {\displaystyle M} , sodass jedes Element aus M {\displaystyle M} in genau einer Menge aus P {\displaystyle P} vorkommt. Für alle natürlichen Zahlen einschließlich der Null n ∈ ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} bezeichnet nun die Bellsche Zahl B n {\displaystyle B_{n}} die Anzahl | Q | {\displaystyle \left|Q\right|} der möglichen verschiedenen Partitionen einer Menge mit der Mächtigkeit n {\displaystyle n} , wobei Q {\displaystyle Q} die Menge aller möglichen Partitionen darstellt. Formal:

| M | = n {\displaystyle \left|M\right|=n}

∀ ∀ P ∈ ∈ Q : ⋃ ⋃ a ∈ ∈ P a = M {\displaystyle \forall P\in Q:\bigcup _{a\in P}a=M}

∀ ∀ P ∈ ∈ Q : ∀ ∀ a ∈ ∈ P : a ≠ ≠ ∅ ∅ {\displaystyle \forall P\in Q:\forall a\in P:a\neq \emptyset }

∀ ∀ P ∈ ∈ Q : ∀ ∀ a , b ∈ ∈ P : ( a ≠ ≠ b ⟹ ⟹ a ∩ ∩ b = ∅ ∅ ) {\displaystyle \forall P\in Q:\forall a,b\in P:(a\neq b\Longrightarrow a\cap b=\emptyset )}

B n := | Q | {\displaystyle B_{n}:=\left|Q\right|}

Die Bellsche Zahl mit dem Index 0, B 0 {\displaystyle B_{0}} , – also die Anzahl der Partitionen der leeren Menge ∅ ∅ {\displaystyle \emptyset } – ist 1, weil die einzige Partition der leeren Menge wieder die leere Menge selbst ist, Q ( ∅ ∅ ) = { P 1 } = { ∅ ∅ } {\displaystyle Q(\emptyset )=\{P_{1}\}=\{\emptyset \}} . Dies ist so, weil alle Aussagen mit dem Allquantor über die Elemente der leeren Menge wahr sind (siehe leere Menge).

→

Hauptartikel

:

Multiplikative Partition

Sei N {\displaystyle N} eine quadratfreie Zahl, ω ω : N → → N {\displaystyle \omega :\mathbb {N} \rightarrow \mathbb {N} } die Funktion zur Bestimmung der Anzahl der einzigartigen Primfaktoren und n = ω ω ( N ) {\displaystyle n=\omega (N)} .

Dann ist B n {\displaystyle B_{n}} die Anzahl der unterschiedlichen multiplikativen Partitionen von N {\displaystyle N} .

Sei zum Beispiel N = 30 {\displaystyle N=30} , so ist n = ω ω ( 30 ) = 3 {\displaystyle n=\omega (30)=3} (da 30 aus den drei Primfaktoren 2, 3 und 5 besteht) und B 3 = 5 {\displaystyle B_{3}=5} ist damit die Anzahl der multiplikativen Partitionen. Diese lauten:

30 = 2 × × 15 = 3 × × 10 = 5 × × 6 = 2 × × 3 × × 5 {\displaystyle 30=2\times 15=3\times 10=5\times 6=2\times 3\times 5}

Für die Bellschen Zahlen gilt diese Rekursionsformel:

B n + 1 = ∑ ∑ k = 0 n ( n k ) B k {\displaystyle B_{n+1}=\sum _{k=0}^{n}{{n \choose k}B_{k}}}

Die Dobińskische Formel (Dobiński 1877)cite-ref-1[1]

B n = 1 e ∑ ∑ k = 0 ∞ ∞ k n k ! {\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}}

erlaubt die explizite Definition der Bellschen Zahlen für alle n ≥ 0. Sie wurde nach dem polnischen Mathematiker Donald Gabriel Dobińskicite-ref-2[2] benannt.

Ihre Äquivalenz zur obigen Rekursionsformel lässt sich durch vollständige Induktion beweisen:

Sei

f ( n ) = 1 e ∑ ∑ k = 0 ∞ ∞ k n k ! {\displaystyle f(n)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}} .

Dann gilt:

f ( 0 ) = 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! = 1 {\displaystyle f(0)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}=1}

sowie für n ≥ 0:

f ( n + 1 ) = 1 e ∑ ∑ k = 0 ∞ ∞ k n + 1 k ! = 1 e ∑ ∑ k = 1 ∞ ∞ k n + 1 k ! = 1 e ∑ ∑ k = 0 ∞ ∞ ( k + 1 ) n + 1 ( k + 1 ) ! = 1 e ∑ ∑ k = 0 ∞ ∞ ( k + 1 ) n k ! = {\displaystyle f(n+1)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n+1}}{k!}}={\frac {1}{e}}\sum _{k=1}^{\infty }{\frac {k^{n+1}}{k!}}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {(k+1)^{n+1}}{(k+1)!}}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {(k+1)^{n}}{k!}}=}

= 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! ∑ ∑ m = 0 n ( n m ) k m = ∑ ∑ m = 0 n ( n m ) 1 e ∑ ∑ k = 0 ∞ ∞ k m k ! = ∑ ∑ m = 0 n ( n m ) f ( m ) {\displaystyle ={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{m=0}^{n}{\binom {n}{m}}k^{m}=\sum _{m=0}^{n}{\binom {n}{m}}{\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{m}}{k!}}=\sum _{m=0}^{n}{\binom {n}{m}}f(m)}

Aus

f ( 0 ) = 1 {\displaystyle f(0)=1} und

∀ ∀ n ∈ ∈ N 0 : f ( n + 1 ) = ∑ ∑ m = 0 n ( n m ) f ( m ) {\displaystyle \forall n\in \mathbb {N} _{0}:f(n+1)=\sum _{m=0}^{n}{\binom {n}{m}}f(m)} folgt schließlich:

∀ ∀ n ∈ ∈ N 0 : f ( n ) = B n {\displaystyle \forall n\in \mathbb {N} _{0}:f(n)=B_{n}}

Somit ist B n {\displaystyle B_{n}} auch das n {\displaystyle n} -te Moment einer Poisson-Verteilung mit Erwartungswert 1.

Die erzeugende Funktion der Bellzahlen ist wie folgt darstellbar:

∑ ∑ n = 0 ∞ ∞ B n x n = 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! ( 1 − − k x ) {\displaystyle \sum _{n=0}^{\infty }B_{n}\,x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!\,(1-kx)}}}

Die exponentiell erzeugende Funktion lautet:

∑ ∑ n = 0 ∞ ∞ B n n ! x n = e e x − − 1 {\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}\,x^{n}=e^{e^{x}-1}}

Dies folgt aus der genannten Dobiński-Formel:

∑ ∑ n = 0 ∞ ∞ B n n ! x n = ∑ ∑ n = 0 ∞ ∞ 1 n ! [ 1 e ∑ ∑ k = 0 ∞ ∞ k n k ! ] x n = 1 e ∑ ∑ n = 0 ∞ ∞ ∑ ∑ k = 0 ∞ ∞ k n k ! n ! x n = 1 e ∑ ∑ k = 0 ∞ ∞ ∑ ∑ n = 0 ∞ ∞ k n k ! n ! x n = 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! ∑ ∑ n = 0 ∞ ∞ ( k x ) n n ! = {\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}x^{n}=\sum _{n=0}^{\infty }{\frac {1}{n!}}{\biggl [}{\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}}{\biggr ]}x^{n}={\frac {1}{e}}\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\frac {k^{n}}{k!n!}}x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }\sum _{n=0}^{\infty }{\frac {k^{n}}{k!n!}}x^{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\sum _{n=0}^{\infty }{\frac {(kx)^{n}}{n!}}=}

= 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! exp ⁡ ⁡ ( k x ) = 1 e ∑ ∑ k = 0 ∞ ∞ 1 k ! exp ⁡ ⁡ ( x ) k = 1 e exp ⁡ ⁡ [ exp ⁡ ⁡ ( x ) ] = exp ⁡ ⁡ [ exp ⁡ ⁡ ( x ) − − 1 ] {\displaystyle ={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\exp(kx)={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {1}{k!}}\exp(x)^{k}={\frac {1}{e}}\exp[\exp(x)]=\exp[\exp(x)-1]}

Die Bellschen Zahlen genügen der Kongruenz (Touchard 1933)cite-ref-3[3]

B p k + n ≡ ≡ k B n + B n + 1 ( mod p ) {\displaystyle B_{p^{k}+n}\equiv k\,B_{n}+B_{n+1}\ ({\text{mod }}p)}

für natürliche Zahlen k {\displaystyle k} und Primzahlen p {\displaystyle p} , insbesondere B p k ≡ ≡ k + 1 ( mod p ) {\displaystyle B_{p^{k}}\equiv k+1\ ({\text{mod }}p)} und B p ≡ ≡ 2 ( mod p ) {\displaystyle B_{p}\equiv 2\ ({\text{mod }}p)} und, nach Iteration,cite-ref-4[4]

B 1 + p + … … + p p − − 1 + n ≡ ≡ B n ( mod p ) . {\displaystyle B_{1+p+\ldots +p^{p-1}+n}\equiv B_{n}\ ({\text{mod }}p).}

Es wird vermutet, dass 1 + p + ⋯ ⋯ + p p − − 1 {\displaystyle 1+p+\dots +p^{p-1}} die kleinste Periode von B n ( mod p ) {\displaystyle B_{n}\ ({\text{mod }}p)} ist.cite-ref-5[5]cite-ref-6[6] Für Primzahlen p > 2 {\displaystyle p>2} ist

B p k + 1 n ≡ ≡ B p k n + 1 ( mod p k + 1 ) , {\displaystyle B_{p^{k+1}n}\equiv B_{p^{k}n+1}\ ({\text{mod }}p^{k+1}),}

für p = 2 {\displaystyle p=2} gilt die Kongruenz ( mod p k ) {\displaystyle ({\text{mod }}p^{k})} .cite-ref-7[7]

Da die Stirling-Zahl S ( n , k ) {\displaystyle S(n,k)} zweiter Art die Anzahl der k {\displaystyle k} -Partitionen einer n {\displaystyle n} -elementigen Menge ist, gilt

B n = ∑ ∑ k = 0 n S ( n , k ) . {\displaystyle B_{n}=\sum _{k=0}^{n}S(n,k).}

Für die Bellzahlen sind verschiedene asymptotische Formeln bekannt, etwa

B n ∼ ∼ n − − 1 / 2 ( λ λ ( n ) ) n + 1 / 2 e λ λ ( n ) − − n − − 1 {\displaystyle B_{n}\sim n^{-1/2}\ {\bigl (}\lambda (n){\bigr )}^{n+1/2}\ e^{\lambda (n)-n-1}} mit λ λ ( n ) = e W ( n ) = n W ( n ) {\displaystyle \lambda (n)=e^{W(n)}={\frac {n}{W(n)}}}

mit der Lambert-W-Funktion W {\displaystyle W} .

Die Bellschen Zahlen lassen sich intuitiv durch das Bellsche Dreieck erzeugen, welches – wie das Pascalsche Dreieck – aus natürlichen Zahlen besteht und pro Zeile ein Element bzw. eine Spalte mehr besitzt. Das Bellsche Dreieck wird gelegentlich auch Aitkens array (nach Alexander Aitken) oder Peirce-Dreieck (nach Charles Sanders Peirce) genannt.

Es wird nach den folgenden Regeln konstruiert:

1. Die erste Zeile hat nur ein Element: Die Eins: x 1 , 1 = 1 {\displaystyle \ x_{1,1}=1\ } .

2. Jede folgende Zeile hat jeweils ein Element mehr als die vorherige Zeile, d. h. die n {\displaystyle n} -te Zeile hat n {\displaystyle n} Elemente.

3. Das jeweils erste Element jeder Zeile hat den gleichen Wert wie das letzte Element der vorherigen Zeile: x k + 1 , 1 = x k , k {\displaystyle \ x_{k+1,1}=x_{k,k}\ } .

4. Das k {\displaystyle k} -te Elemente der n. Zeile (für 1 < k ≤ ≤ n {\displaystyle 1<k\leq n} ) ist gleich der Summe des links stehenden ( k − − 1 ) {\displaystyle (k-1)} -ten Elements derselben Zeile und des ( k − − 1 ) {\displaystyle (k-1)} -ten Elements der vorherigen Zeile (also jene mit der Nummer n − − 1 {\displaystyle n-1} ): x k , n = x k , n − − 1 + x k − − 1 , n − − 1 {\displaystyle \ x_{k,n}=x_{k,n-1}+x_{k-1,n-1}\ } .

5. B n {\displaystyle B_{n}} ist nun das n {\displaystyle n} -te Element aus der n {\displaystyle n} -ten Zeile x n , n _ _ {\displaystyle {\underline {x_{n,n}}}} (bzw. das erste Element aus der n + 1 {\displaystyle n+1} -ten Zeile x n + 1 , 1 {\displaystyle x_{n+1,1}} ).

Die ersten sechs Zeilen, erzeugt nach diesen Regeln, sehen wie folgt aus:

1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 052 067 087 114 151 203 203 …

Wegen des dritten Schritts sind die Bellschen Zahlen sowohl auf der linken als auch auf der rechten Kante des Dreiecks zu sehen, lediglich mit dem Unterschied, dass in der n {\displaystyle n} -ten Zeile links die Zahl B n − − 1 {\displaystyle B_{n-1}} und rechts die Zahl B n {\displaystyle B_{n}} steht.

Im Jahre 1978 formulierte Martin Gardner die Frage, ob unendlich viele Bellsche Zahlen auch Primzahlen sind. Die ersten Bellschen Primzahlen sind:

| n {\displaystyle n} (Folge A051130 in OEIS ) | B n {\displaystyle B_{n}} (Folge A051131 in OEIS ) |

|---|---|

| 2 | 2 |

| 3 | 5 |

| 7 | 877 |

| 13 | 27644437 |

| 42 | 35742549198872617291353508656626642567 |

| 55 | 359334085968622831041960188598043661065388726959079837 |

Die nächste Bellsche Primzahl ist B 2841 {\displaystyle B_{2841}} , die etwa 9,307 40105 × × 10 6538 {\displaystyle 9{,}30740105\times 10^{6538}} beträgt.cite-ref-8[8] Sie ist auch die aktuell größte bekannte Bellsche Primzahl (Stand: 5. August 2018). Im Jahre 2002 zeigte Phil Carmody zunächst, dass es sich bei dieser Zahl wahrscheinlich um eine Primzahl (eine sogenannte PRP-Zahl) handelt, sie also entweder tatsächlich eine echte Primzahl oder eine Pseudoprimzahl ist. Nach einer 17-monatigen Berechnung mit Marcel Martins Programm „Primo“, welches mit einem Verfahren mit elliptischen Kurven arbeitet, bewies Ignacio Larrosa Cañestro schließlich im Jahre 2004, dass es sich bei B 2841 {\displaystyle B_{2841}} um eine Primzahl handelt. Gleichzeitig schloss er weitere Bellsche Primzahlen bis zu einer Grenze von B 6000 {\displaystyle B_{6000}} aus, welche später von Eric Weisstein auf B 30447 {\displaystyle B_{30447}} angehoben wurde.

cite-note-11. ↑ G. Dobiński: Summirung der Reihe ∑ ∑ n m n ! {\displaystyle \textstyle \sum {\frac {n^{m}}{n!}}} für m = 1 , 2 , 3 , 4 , 5 , … … {\displaystyle m=1,2,3,4,5,\ldots } , Grunert-Archiv 61, 1877, S. 333–336

cite-note-22. ↑ YYiki: G. Dobínski. Abgerufen am 7. September 2021.

cite-note-33. ↑ Jacques Touchard: Propriétés arithmétiques de certains nombres récurrents, Annales de la Société scientifique de Bruxelles A 53, 1933, S. 21–31 (französisch)

cite-note-44. ↑ Marshall Hall: Arithmetic properties of a partition function, Bulletin of the AMS 40, 1934, S. 387 (englisch; nur Abstract)

cite-note-55. ↑ Christian Radoux: Nombres de Bell, modulo p premier, et extensions de degré p de Fp, Comptes rendus hebdomadaires des séances de l’académie des sciences 281 A, 1975, S. 879–882 (französisch)

cite-note-66. ↑ Peter L. Montgomery, Sangil Nahm, Samuel S. Wagstaff: The period of the Bell numbers modulo a prime (PDF-Datei, 168 kB), Mathematics of computation 79, 2010, S. 1793–1800 (englisch)

cite-note-77. ↑ Anne Gertsch, Alain M. Robert: Some congruences concerning the Bell numbers, Bulletin of the Belgian Mathematical Society – Simon Stevin 3, 1996, S. 467–475 (englisch)

cite-note-88. ↑ 93074010508593618333...(6499 other digits)...83885253703080601131 auf Prime Pages. Abgerufen am 5. August 2018.

• Eric Temple Bell: Exponential Numbers, The American Mathematical Monthly 41, 1934, S. 411–419

• Jacques Touchard: Nombres exponentiels et nombres de Bernoulli, Canadian Journal of Mathematics 8, 1956, S. 305–320 (französisch)

• Eric W. Weisstein: Bell Number und Dobiński’s Formula. In MathWorld (englisch)

• Bell numbers bei The Wolfram Functions Site (englisch; mit Berechnungsmöglichkeit)

• Set Partitions: Bell Numbers in der NIST Digital Library of Mathematical Functions (englisch)

• Peter Luschny: Set partitions and Bell numbers (englisch). Eine Zusammenfassung von OEIS-Folgen zu den Bellzahlen im OEIS Wiki.